class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z----"]
        m = {}
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == '-':
                    continue
                m[board[i][j]] = (i, j)
        res = ""
        x = 0
        y = 0
        for s in target:
            i, j = m[s]
            diffX = x-i
            diffY = y-j
            if diffX > 0:
                vertical = 'U'
            elif diffX < 0:
                vertical = 'D'
            else:
                vertical = ''
            if diffY > 0:
                horizontal = 'L'
            elif diffY < 0:
                horizontal = 'R'
            else:
                horizontal = ''
            if board[x][j] == '-':
                for _ in range(abs(diffX)):
                    res += vertical
                for _ in range(abs(diffY)):
                    res += horizontal
            else:
                for _ in range(abs(diffY)):
                    res += horizontal
                for _ in range(abs(diffX)):
                    res += vertical

            if board[i][j] == s:
                res += '!'
            x = i
            y = j

        return res
